package subjectlist;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.Arrays;

/**
 * 题目描述：
 * 给定一个字符串，找出这个字符串中最长的重复子串。
 * 例如，给定字符串“banana”，子字符串“ana”出现两次，因此最长的重复子串为“ana”
 */
public class Q求一个串中出现的第一个最长重复子串 {


    /**
     *后缀数组是一个字符串的所有后缀的排序数组。后缀是指从某个位置i开始到整个串末尾结束的一个子串。
     * 字符串r的从第i个字符开始的后缀表示为Suffix（i），
     * 也就是Suffix（i）=r[i..len（r）]。例如，字符串“banana”的所有后缀如下
     *
     * 所以“banana”的后缀数组为：{5, 3, 1, 0, 4,2}。由此可以把找字符串的重复子串的问题，
     * 转换为从后缀排序数组中，通过对比相邻的两个子串的公共串的长度找出最长的公共串的问题。
     * 在上例中3：ana与1：anana的最长公共子串为ana。这也就是这个字符串的最长公共子串
     */


    //找出最长公共子串的长度
    private int maxPrefix(String s1,String s2){
        int i=0;
        while (i < s1.length() && i < s2.length()) {
            if (s1.charAt(1) == s2.charAt(i)) {
                i++;
            }else {
                break;
            }
        }
        return i;
    }

    //获取最长的公共子串
    public String getMaxCommonStr(String txt){
        int n=txt.length();
        //用来存储后缀数组
        String[]suffixes=new String[n];
        int tmp;
        int longestSubStrLen=0;
        String longestSubStr=null;
        int i;

        //获取到后缀数组
        for (i = 0; i <n ; i++) {
            suffixes[i]=txt.substring(i);
        }
        //对后缀数组排序
        Arrays.sort(suffixes);
        for (i = 1; i < n ; i++) {
            tmp=maxPrefix(suffixes[i],suffixes[i-1]);
            if(tmp>longestSubStrLen){
                longestSubStrLen=tmp;
                longestSubStr=suffixes[i].substring(0,i+1);
            }
        }
        return longestSubStr;
    }


    /**
     * 这种方法下生成后缀数组的复杂度为O（N），排序的算法复杂度为 O（NlogN*N），
     * 最后比较相邻字符串的操作的时间复杂度为O（N）。所以，算法的时间复杂度为O（NlogN*N）。
     * 此外，由于申请了长度为N的额外的存储空间，因此空间复杂度为O（N
     * @param args
     */
    public static void main(String[] args) {

        String txt="banana";
        Q求一个串中出现的第一个最长重复子串 c=new Q求一个串中出现的第一个最长重复子串();
        System.out.println("最长的公共子串为："+c.getMaxCommonStr(txt));
    }
}
